
// 140. 单词拆分 II
function wordBreak(s:string, wordDict:string[]):string[] {
    const cache = new Map<number,Array<string>>()

    const dict = new Set<string>()
    for(let w of wordDict){
        dict.add(w)
    }

    type ANS = Array<string>|null

    function search(index:number):void{
        let tmp:string[] = []
        for(let i= index;i<s.length;i++){
            const sub = s.substring(index,i+1)
            if(dict.has(sub)){
                if(i==s.length-1){
                    tmp.push(sub)
                    break
                }
                else if(!cache.has(i+1)){
                    search(i+1)
                }
                let c = cache.get(i+1)
                if(c){
                    for(let t of c!){
                        tmp.push(`${sub} ${t}`)
                    }
                }
            }
        }
        cache.set(index,tmp)
    }
    search(0)
    return cache.get(0)||[]
};


// 57. 插入区间
function insert(intervals: number[][], newInterval: number[]): number[][] {
    /**
     * newInterval和一共三种位置
     * 在区间左侧无交集
     * 在区间右侧无交集
     * 和区间有交集
     */
    let l = newInterval[0]
    let h = newInterval[1]
    let start = Number.MIN_VALUE
    let end = Number.MIN_VALUE
    let ans:number[][] = []
    let PUSH = false
    let i = 0
    for(i=0;i<intervals.length;i++){
        if(intervals[i][0]>h){
            ans.push(newInterval)
            ans.push(...intervals.slice(i))
            return ans
        }
        else if(intervals[i][1]<l) ans.push(intervals[i])
        else{
            start = Math.min(intervals[i][0],l)
            end = Math.max(intervals[i][1],h)
            break
        }
    }
    if(start==Number.MIN_VALUE) {
        ans.push(newInterval)
        return ans
    }
    for(;i<intervals.length;i++){
        if(intervals[i][0]>h){
            ans.push([start,end])
            ans.push(intervals[i])
            PUSH = true
            break
        }
        else if(intervals[i][1]>=h){
            ans.push([start,intervals[i][1]])
            PUSH = true
            break
        }
    }
    if(!PUSH) ans.push([start,end])
    else ans.push(...intervals.slice(i+1))
    return ans
};


// 5554. 能否连接形成数组
function canFormArray(arr: number[], pieces: number[][]): boolean {
    let map = new Map<number,number>()
    pieces.forEach((v,i)=>{
        map.set(v[0],i)
    })
    let index = 0
    let used = 0
    while(index<arr.length){
        let fisrt = arr[index]
        if(!map.has(fisrt)) return false
        let i = map.get(fisrt)!
        used++
        for(let j=0;j<pieces[i].length;j++){
            if(arr[index++]!=pieces[i][j]) return false
        }
    }
    return used ==pieces.length
};

// 1641. 统计字典序元音字符串的数目
function countVowelStrings(n: number): number {
    //简单dp，还可以排列组合
    let a = 1
    let e = 1
    let i = 1
    let o = 1
    let u = 1
    for(let j=2;j<=n;j++){
        a+=(e+i+o+u)
        e+=(i+o+u)
        i+=(o+u)
        o+=u
    }
    return a+e+i+o+u
};


// 面试题60. n个骰子的点数
function dicesProbability(n: number): number[] {
    let dp = new Array(n+1).fill(false).map(v=>new Array(n*6+1).fill(0))
    dp[1].fill(1)
    for(let i=2;i<n+1;i++){
        for(let j=i;j<=6*i;j++){
            for(let k = 1 ;k<=6;k++){
                if(j-k>0&&j-k<=6*(i-1)) dp[i][j]+=dp[i-1][j-k]
            }
        }
    }
    let ans:number[] = []
    let sum = Math.pow(6,n)
    for(let i=1;i<=6*n;i++){
        let it = dp[n][i]
        if(it!=0){
            ans.push(it/sum)
        }
    }
    return ans
};

//922. 按奇偶排序数组 II
function sortArrayByParityII(A: number[]): number[] {
    let odd = 1
    let even  = 0
    while(odd<A.length&&even<A.length){
        while(odd<A.length&&A[odd]&1) odd+=2
        while(even<A.length&&!(A[even]&1)) even+=2
        if(odd<A.length&&even<A.length){
            [A[odd],A[even]]=[A[even],A[odd]]
            odd+=2
            even+=2
        }
    }
    return A
}

//328. 奇偶链表
// function oddEvenList(head: ListNode | null): ListNode | null {
//     let even = new ListNode(-1)
//     let odd  = new ListNode(-1)
//     even.next = null
//     odd.next = null
//     let pE:ListNode|null = even
//     let pO:ListNode|null = odd
//     let p = head
//     //!   两步两步向后移动的方法,移动几步就判断几个空
//     while(p!=null&&p.next!=null){
//         pO.next = p
//         pE.next = p.next
//         pO=pO.next
//         pE = pE.next
//         p = p!.next!.next
//     } 
//     if(p!=null){
//         pO.next = p
//         pO=pO.next
//     }
//     pE.next = null
//     pO.next = even.next
//     return odd.next
// };

// 1122. 数组的相对排序
function relativeSortArray(arr1: number[], arr2: number[]): number[] {
    //!本来使用的map+优先队列,优先队列也可以直接排序=>有点类似题解的计数排序
    //题解自定义排序函数的方法
    let map = new Map<number,number>()
    arr2.forEach((v,i)=>{
        map.set(v,i)
    })

    arr1.sort((a,b)=>{
        //arr2有a
        if(map.has(a)){
            if(map.has(b)){
                return map.get(a)! - map.get(b)!
            }else{
                return -1
            }
        }
        //arr2有b没a
        else if(map.has(b)){
            return 1
        }
        //两个都没有
        else{
            return a - b
        }
    })
    return arr1
};

//402. 移掉K位数字
function removeKdigits(num: string, k: number): string {

    //?搜索超时
    // let ans = Number.MAX_VALUE

    // function search(prefix:string,str:string,n:number):void{
    //     if(n==0){
    //         let a  = Number.parseInt(prefix+str)||0
    //         ans = Math.min(ans,a)
    //     }
    //     if(str=='') return
    //     for(let i=0;i<str.length;i++){
    //         search(prefix+str.substring(0,i),str.substring(i+1),n-1)
    //     }
    // }

    // search('',num,k)

    // return ans.toString()
    
    let stack:string[] = []
    let last = '1'
    let del = 0
    for(let c of num){
        if(stack.length==0||c>=''+last){
            stack.push(c)
            last = c
        }
        else{
            while(c<last&&del<k){
                stack.pop()            
                del++
                last = stack[stack.length-1]
            }
            stack.push(c)
            last = c
        }
    }
    let ans =''
    let start = 0
    for(;start<stack.length-(k-del);start++){
        if(stack[start]!='0') break
    }
    for(;start<stack.length-(k-del);start++){
        ans+=stack[start]
    }
    return ans||'0'
};


// 5601. 设计有序流
class OrderedStream {
    private ptr = 1
    private map = new Map<number,string>()
    constructor(private n: number) {
    }

    insert(id: number, value: string): string[] {
        let ans:string[] = []
        this.map.set(id,value)
        if(id==this.ptr){
            let i 
            for(i=id;i<=this.n;i++){
                if(this.map.has(i)) ans.push(this.map.get(i)!)
                else break
            }
            this.ptr = i
        }
        return ans
    }
}

//5602. 将 x 减到 0 的最小操作数
function minOperations(nums: number[], x: number): number {

    // let ans = Number.MAX_VALUE 

    // //[start,end]
    // function search(start:number,end:number,target:number,times:number):void{
    //     if(target==0) ans = Math.min(ans,times)
    //     if(target<0||start>end) return 
    //     search(start+1,end,target-nums[start],times+1)
    //     search(start,end-1,target-nums[end],times+1)
    // }
    
    // search(0,nums.length-1,x,0)

    // return ans == Number.MAX_VALUE? -1 : ans

    //!左右双指针版
    let l =0 
    let h = nums.length-1
    let times= Number.MAX_VALUE
    while(x>0&&l<nums.length){
        x-=nums[l]
        l++
    }
    if(x==0) times = l
    else if (x>0) return -1
    while(h>=0&&l>=0){
        while(x<0){
            l--
            x+=nums[l]
        }
        if(x==0) times = Math.min(times,l+nums.length-1-h)
        x-=nums[h]
        h--
    }
    while(x>0&&h>=0){
        x-=nums[h]
        h--
    }
    if(x==0) times = Math.min(times,nums.length-h-1)
    return times==Number.MAX_VALUE ? -1 : times


    //!滑动窗口版
    // const sum = nums.reduce((s,cur)=>s+cur,0) - x
    // let low =0
    // let high =0
    // let max = -1
    // let cur = 0
    // while(high<nums.length){
    //     while(high<nums.length&&cur<sum){
    //         cur+=nums[high++]
    //     }
    //     if(cur==sum) max = Math.max(max,high-low)
    //     cur-=nums[low++]
    //     if(low>=high) break
    // }
    // return max == -1 ? -1 : nums.length-max
};

// 738. 单调递增的数字
function monotoneIncreasingDigits(N: number): number {
    //!暴力枚举超时，那么只能想办法找规律去生成这个序列

    let str = N.toString()
    //找第一个不满足的位置
    let i 
    for(i=1;i<str.length;i++){
        if(str[i]<str[i-1])break
    }
    if(i==str.length) return N
    //找第一个满足<=后一位减一的
    i--     //第一个需要测试的位
    while(i>=0){
        if(str.charCodeAt(i)<=str.charCodeAt(i+1)-1) break
        i--
    }
    let prifix = str.substring(0,i+1)
    //需要减1的那一位
    let next = String.fromCharCode(str.charCodeAt(i+1)-1)
    //最后补9
    let nine = ''
    let nineCnt = str.length-prifix.length-1
    for(let j=0;j<nineCnt;j++){
        nine+='9'
    }
    return Number.parseInt(prifix+next+nine)
};


// 1030. 距离顺序排列矩阵单元格
function allCellsDistOrder(R: number, C: number, r0: number, c0: number): number[][] {
    /**
     * 虽然不难，但是解法挺多
     *  bfs 和 桶排序  直接的快速排序
     * bfs在图的权值相等的时候找最短路径是好方法
     * 桶排序在序列的值的范围较小的时候挺快 ，相似的还有计数排序
     */
    return []
};

//1657. 确定两个字符串是否接近
function closeStrings(word1: string, word2: string): boolean {
    if(word1.length!=word2.length) return false
    let w1 = new Array(26).fill(0)
    let w2 = new Array(26).fill(0)
    const A = 'a'.charCodeAt(0)

    //统计每个字符的频率
    for(let i=0;i<word1.length;i++){
        const c1 = word1.charCodeAt(i)
        const c2 = word2.charCodeAt(i)
        w1[c1-A]++
        w2[c2-A]++
    }
    //判断两个字符串的字符种类是否相同
    for(let i=0;i<26;i++){
        if((w1[i]==0&&w2[i]!=0)||(w1[i]!=0&&w2[i]==0)) return false
    }

    //判断频次是否相同
    w1.sort((a,b)=>a-b)
    w2.sort((a,b)=>a-b)
    for(let i=0;i<26;i++){
        if(w1[i]!=w2[i]) return false
    }
    return true
};

// 866. 回文素数
function primePalindrome(N: number): number {

    function isPrime(n:number):boolean{
        if(n==1) return false
        for(let i=2;i<=Math.sqrt(n);i++){
            if(n%i==0) return false
        }
        return true
    }

    for(let d = 0;d<=4;d++){
        for(let i= Math.pow(10,d);i<Math.pow(10,d+1);i++){
            let prefix = i.toString()
            let suffix = ''
            for(let i=prefix.length-2;i>=0;i--){
                suffix+=prefix[i]
            }
            let num = Number.parseInt(prefix+suffix)
            if(num>=N&&isPrime(num)) return num
        }

        for(let i=Math.pow(10,d);i<Math.pow(10,d+1);i++){
            let prefix = i.toString()
            let suffix = ''
            for(let i=prefix.length-1;i>=0;i--){
                suffix+=prefix[i]
            }
            let num = Number.parseInt(prefix+suffix)
            if(num>=N&&isPrime(num)) return num
        }

    }
    return -1
};

